import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * 滑动窗口算法框架
 *
 * @author 猿小蔡
 * @date 2022/3/26
 */
public class SlidingWindowFrame {

  /**
   * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
   *
   * <p>在 S(source) 中找到包含 T(target) 中全部字母的一个子串，且这个子串一定是所有可能子串中最短的。
   *
   * <p>最小覆盖子串
   *
   * @see <a href="最小覆盖子串">https://leetcode-cn.com/problems/minimum-window-substring/</a>
   * @param s 输入一个串
   * @param t 包含的全部字母的一个子串
   * @return 最小覆盖子串
   */
  public String minWindow(String s, String t) {
    HashMap<Character, Integer> need = new HashMap<>(); // 用来存储匹配串的字符以及其频率
    HashMap<Character, Integer> window = new HashMap<>(); // 目前窗口中的字符和其出现的频率
    int t_length = t.length(); // 匹配串的长度
    // 统计 匹配串t的字符 和 其出现的频率
    for (int i = 0; i < t_length; i++) {
      need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1); // 获取指定的key对应的 value 如果找不到key 则返回设置的默认值
    }
    int left = 0; // 初始化左指针
    int right = 0; // 初始化右指针
    int valid = 0; // 窗口中 满足need条件的字符个数，如果valid和need.size 大小相同 说明 窗口完全满足条件了 可以选择收缩了
    int start = 0; // 记录最小覆盖子串的起使索引
    int len = Integer.MAX_VALUE; // 记录最小覆盖字串的长度
    // 右指针到达 目标串s的末尾的时候停止
    while (right < s.length()) {
      char c = s.charAt(right); // 获取右指针所在位置的char
      right++; // 右指针右移 窗口扩大
      if (need.containsKey(c)) { // 如果need中包含当前指针所在的字符c
        window.put(c, window.getOrDefault(c, 0) + 1); // 将当前char c 存入对应的window位置
        if (window.get(c).equals(need.get(c))) { // 如果目标map 中的 相对应的 字符数量符 和 当前window中的 对应的字符数量相同 则
          // 符合的valid++
          valid++;
        }
      }
      while (valid == need.size()) { // 如果 window中符合need中的char数量则说明确实找到了可行解
        if (right - left < len) { // 说明现在的子串的长度比 之前记录的长度还要小
          len = right - left; // 更新字串长度记录
          start = left; // 更新起使索引到left
        }
        // 将当前left位置的字符移除窗口
        char d = s.charAt(left);
        // 左移窗口
        left++;
        if (need.containsKey(d)) { // 如果当前移除的字符 存在于 need中 需要对窗口内的数据进行一系列更新
          if (window.get(d).equals(need.get(d))) { // 如果当前需要移除的字符数量 和 need中需要移除的字符数量相同 则将 匹配的字符个数 -1
            valid--;
          }
          window.put(d, window.get(d) - 1); // 将当前的
        }
      }
    }
    // right到达了字符串的末尾
    return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
  }

  /**
   * 给你两个字符串s1和s2 ，写一个函数来判断 s 是否包含 s1的排列。如果是，返回 true ；否则，返回 false 。
   *
   * <p>换句话说，t 的排列之一是 s 的 子串 。
   *
   * <p>相当给你一个 S 和一个 T，请问你 S 中是否存在一个子串，包含 T 中所有字符且不包含其他字符？
   *
   * <p>字符串排列
   *
   * @see <a href="字符串排列">https://leetcode-cn.com/problems/permutation-in-string/</a>
   * @param t 条件字符串
   * @param s 输入一个串
   * @return true：存在，false：不存在
   */
  public boolean checkInclusion(String t, String s) {
    HashMap<Character, Integer> need = new HashMap<>(); // 目标 t
    HashMap<Character, Integer> window = new HashMap<>(); // 滑动窗口记录
    int left = 0; // 左指针
    int right = 0; // 右指针
    int valid = 0; // 滑动窗口中的符合的字符个数
    // 符合条件1：窗口中包含所有s1中的字符
    // 符合条件2：窗口中包含的s1的字符的数量都和s1中的一样
    // 将s1中的字符hash化
    for (int i = 0; i < t.length(); i++) {
      need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1);
    }
    // 停止标志 right指针超出s2的右边界
    while (right < s.length()) {
      char c = s.charAt(right); // 获取right位置的字符
      right++; // right指针右移
      // 窗口内数据更新
      if (need.containsKey(c)) { // need中确实包含当前right指针指向的这个字符
        window.put(c, window.getOrDefault(c, 0) + 1);
        if (window.get(c).equals(need.get(c))) {
          valid++;
        }
      }
      // 判断window收缩 左移条件是滑动窗口大小 大于等于字串长度
      while (right - left >= t.length()) {
        if (valid == need.size()) {
          return true; // 符合的字符种类和数量相同
        }
        // 如果还没符合 left右移 缩小滑动窗口
        char d = s.charAt(left);
        left++;
        if (need.containsKey(d)) {
          if (window.get(d).equals(need.get(d))) {
            valid--;
          }
          window.put(d, window.get(d) - 1);
        }
      }
    }
    return false;
  }

  /**
   * 给定两个字符串 和 t，找到 中所有 t 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
   *
   * <p><t>异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
   *
   * <p><t>相当于，输入一个串 S，一个串 T，找到 S 中所有 T 的排列，返回它们的起始索引。
   *
   * <p>找所有字母异位词
   *
   * @see <a href="找所有字母异位词">https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/</a>
   * @param s 输入一个串
   * @param t 条件字符串
   * @return 索引集合
   */
  public List<Integer> findAnagrams(String s, String t) {
    HashMap<Character, Integer> need = new HashMap<>(), window = new HashMap<>();
    for (int i = 0; i < t.length(); i++) {
      need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1);
    }
    int left = 0;
    int right = 0;
    int valid = 0;
    List<Integer> result = new ArrayList<>(); // 记录开始位置
    while (right < s.length()) {
      char c = s.charAt(right); // 获取当前right所在位置的字符
      right++; // 窗口 向右扩展
      if (need.containsKey(c)) {
        window.put(c, window.getOrDefault(c, 0) + 1);
        if (window.get(c).equals(need.get(c))) {
          valid++;
        }
      }
      // 窗口收缩时间
      while (right - left >= t.length()) {
        if (valid == need.size()) { // 此处一定要写need.size() 因为存在重复的字符
          result.add(left); // 将left起使位置加入到 result中
        }
        char d = s.charAt(left);
        left++; // 右移
        if (need.containsKey(d)) {
          if (window.get(d).equals(need.get(d))) {
            valid--;
          }
          window.put(d, window.get(d) - 1); // 更新window中d字符的个数
        }
      }
    }
    return result;
  }

  /**
   * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
   *
   * <p>无重复字符的最长子串
   *
   * @see <a href="无重复字符的最长子串">https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/</a>
   * @param s 字符串
   * @return 最长字符串长度
   */
  public static int lengthOfLongestSubstring(String s) {
    HashMap<Character, Integer> window = new HashMap<>();
    int left = 0, right = 0;
    int res = 0;
    while (right < s.length()) {
      // c 是移入窗口的字符
      char c = s.charAt(right);
      // 窗口右移
      right++;
      // 更新窗口的一系列数据
      window.put(c, window.getOrDefault(c, 0) + 1);
      // 判断左侧窗口是否需要收缩
      while (window.get(c) > 1) {
        // d 是移出窗口的字符
        char d = s.charAt(left);
        // 窗口右移
        left++;
        // 更新窗口的一系列数据
        window.put(d, window.get(d) - 1);
      }
      // 这里更新最长子串的长度
      int len = right - left;
      res = Math.max(res, len);
    }
    return res;
  }

  /**
   * 滑动窗口算法框架
   *
   * @see <a href="滑动窗口算法框架">https://labuladong.gitee.io/algo/2/22/60/</a>
   * @param s 输入一个串
   * @param t 一个串
   */
  public static void slidingWindow(String s, String t) {
    HashMap<Character, Integer> need = new HashMap<>(), window = new HashMap<>();
    for (int length = t.length(); length > 0; length--) {
      char c = t.charAt(length);
      need.put(c, need.getOrDefault(c, 0) + 1);
    }
    int left = 0, right = 0;
    int valid = 0;
    while (right < s.length()) {
      // c 是将移入窗口的字符
      char c = s.charAt(right);
      // 右移（增大）窗口
      right++;
      // 进行窗口内数据的一系列更新
      // ...
      // debug 输出的位置
      System.out.printf("window: [%d, %d)\n", left, right);
      // ********************

      // 判断左侧窗口是否要收缩
      // while (window needs shrink){
      // // d 是将移出窗口的字符
      // char d = s.charAt(left);
      // // 左移（缩小）窗口
      // left++;
      // // 进行窗口内数据的一系列更新
      // // ...
      // }
    }
  }

}
